package com.xzz;


/**
 * @author 黄会准
 * @since 2020-12-03
 */
public class KthLargest {
    private static int ans = 0, cnt = 0;
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode n3 = new TreeNode(3);
        TreeNode n6 = new TreeNode(6);
        TreeNode n2 = new TreeNode(2);
        TreeNode n4 = new TreeNode(4);
        TreeNode n1 = new TreeNode(1);
        root.left = n3;
        root.right = n6;
        n3.left = n2;
        n3.right = n4;
        n2.left = n1;
        System.out.println(kthLargest(root,3));
    }
    public static int kthLargest(TreeNode root, int k) {
        dfs(root, k);
        return ans;
    }

    private static void dfs(TreeNode root, int k) {
        if(root == null) return ;
        dfs(root.right, k);
        if(++cnt == k) {
            ans = root.val;
        }
        dfs(root.left, k);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
